#include <stdio.h>
#include <stdlib.h>

/* 二叉树结点定义 */
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

/* 1. 根据先序 + 中序 序列构建二叉树（通用） */
BiTree Build_PreIn(int preorder[], int preL, int preR, int inorder[], int inL, int inR)
{
    if (preL > preR) // 子区间空
        return NULL;

    int rootVal = preorder[preL];
    BiTree root = (BiTree)malloc(sizeof(BiTNode)); // 分配新结点
    root->data = rootVal;
    root->lchild = root->rchild = NULL;

    // 在 inorder 中找到根结点位置
    int k = inL;
    while (k <= inR && inorder[k] != rootVal)
        k++;
    int leftLen = k - inL; // 左子树结点数

    // 递归构建左右子树
    root->lchild = Build_PreIn(preorder, preL + 1, preL + leftLen,
                               inorder, inL, k - 1);
    root->rchild = Build_PreIn(preorder, preL + leftLen + 1, preR,
                               inorder, k + 1, inR);
    return root;
}

BiTree BuildTree_PreIn(int preorder[], int inorder[], int len)
{
    return Build_PreIn(preorder, 0, len - 1, inorder, 0, len - 1);
}

/* 2. 根据中序 + 后序 序列构建二叉树（通用） */
BiTree Build_InPost(int inorder[], int inL, int inR,
                    int postorder[], int postL, int postR)
{
    if (postL > postR)
        return NULL;

    int rootVal = postorder[postR];
    BiTree root = (BiTree)malloc(sizeof(BiTNode));
    root->data = rootVal;
    root->lchild = root->rchild = NULL;

    // 在 inorder 中找到根
    int k = inL;
    while (k <= inR && inorder[k] != rootVal)
        k++;
    int leftLen = k - inL;

    // 递归构建左右子树
    root->lchild = Build_InPost(inorder, inL, k - 1,
                                postorder, postL, postL + leftLen - 1);
    root->rchild = Build_InPost(inorder, k + 1, inR,
                                postorder, postL + leftLen, postR - 1);
    return root;
}

BiTree BuildTree_InPost(int inorder[], int postorder[], int len)
{
    return Build_InPost(inorder, 0, len - 1, postorder, 0, len - 1);
}

/* 3. 根据先序 + 后序 序列构建二叉树（仅满二叉树可用） */
BiTree Build_PrePost(int preorder[], int postorder[], int len)
{
    if (len <= 0)
        return NULL;

    BiTree root = (BiTree)malloc(sizeof(BiTNode));
    root->data = preorder[0];
    root->lchild = root->rchild = NULL;

    if (len == 1) // 只有根
        return root;

    int leftRootVal = preorder[1];
    // 在后序中找到左子树根的位置
    int i = 0;
    while (i < len && postorder[i] != leftRootVal)
        i++;
    int leftLen = i + 1; // 左子树结点数

    // 递归构建左右子树
    root->lchild = Build_PrePost(preorder + 1, postorder, leftLen);
    root->rchild = Build_PrePost(preorder + 1 + leftLen,
                                 postorder + leftLen, len - leftLen - 1);
    return root;
}

/* 统一树形输出 */
void PrintTreeShape(BiTree root, int depth)
{
    if (root == NULL) // 空结点直接返回
        return;
    // 先打印右子树，保证树形向左展开
    PrintTreeShape(root->rchild, depth + 1);

    // 根据 depth 输出缩进
    for (int i = 0; i < depth; i++)
        printf("    "); // 每级缩进 4 个空格

    printf("%d\n", root->data); // 打印当前结点值

    // 再打印左子树
    PrintTreeShape(root->lchild, depth + 1);
}

int main()
{
    // 示例遍历序列（满二叉树）
    int preorder[] = {1, 2, 4, 5, 3, 6, 7};
    int inorder[] = {4, 2, 5, 1, 6, 3, 7};
    int postorder[] = {4, 5, 2, 6, 7, 3, 1};
    int len = 7;

    // 1) 先序+中序 构建
    BiTree T1 = BuildTree_PreIn(preorder, inorder, len);
    printf("Tree built from Pre+In:\n");
    PrintTreeShape(T1, 0);
    printf("\n");

    // 2) 中序+后序 构建
    BiTree T2 = BuildTree_InPost(inorder, postorder, len);
    printf("Tree built from In+Post:\n");
    PrintTreeShape(T2, 0);
    printf("\n");

    // 3) 先序+后序 构建（仅限满二叉树）
    BiTree T3 = Build_PrePost(preorder, postorder, len);
    printf("Tree built from Pre+Post:\n");
    PrintTreeShape(T3, 0);
    printf("\n");

    return 0;
}
